#include <string>
#include <sstream>
#include <omp.h>
#include "BigNum.h"
#include "BaseConverter.h"
#include "globals.h"

using namespace std;

const BaseConverter& BigNum::dec2bin = BaseConverter::DecimalToBinaryConverter();
const BaseConverter& BigNum::bin2dec = BaseConverter::BinaryToDecimalConverter();

bool BigNum::operator<(const BigNum& bn) const
{
	if (this->size < bn.size)
	{
		return true;
	}
	else if (this->size > bn.size)
	{
		return false;
	}
	else // this->size == bn.size
	{
		for (int i = this->size; i > 0; i--)
		{
			if (this->pIntArray[i] < bn.pIntArray[i])
			{
				return true;
			}
			else if (this->pIntArray[i] > bn.pIntArray[i])
			{
				return false;
			}
		}
	}

	// if we get here *this == bn
	return false;
}

BigNum& BigNum::operator=(const BigNum& bn)
{
	if (this != &bn)
	{
		pIntArrayType* newArray = new pIntArrayType[bn.size];

		memcpy(newArray,bn.pIntArray,bn.size  * sizeof(pIntArrayType));

		this->bIsPositive = bn.bIsPositive;
		this->size = bn.size;
		this->capacity = this->size;

		delete[] this->pIntArray;

		this->pIntArray = newArray;
	}

	return *this;
}

BigNum::BigNum(const BigNum& bn)
	:bIsPositive(bn.bIsPositive),
	 size(bn.size),
	 capacity(bn.size)
{
	pIntArrayType* newArray = new pIntArrayType[bn.size];
	memcpy(newArray,bn.pIntArray,bn.size * sizeof(pIntArrayType));
	this->pIntArray = newArray;
}

void BigNum::resizeArray(unsigned int newCapacity, bool copyValue)
{
	if (this->capacity < newCapacity)
	{
		pIntArrayType* newArray = new pIntArrayType[newCapacity];

		if (copyValue)
		{
			memcpy(newArray,this->pIntArray,this->size * sizeof(pIntArrayType));
			delete[] this->pIntArray;
		}
		else
		{
			delete[] this->pIntArray;
		}

		this->pIntArray = newArray;
		this->capacity = newCapacity;
	}
}

void BigNum::Add(const BigNum &bn1, const BigNum &bn2, BigNum &result, int num_threads)
{
	if (bn1.IsPositive() && bn2.IsPositive())
	{
		BigNum::addNoCheck(bn1, bn2, result, num_threads);
		result.bIsPositive = true;
	}
	else if (bn1.IsPositive() && !bn2.IsPositive())
	{
		if (bn1 < bn2)
		{
			BigNum::subtractNoCheck(bn2, bn1, result, num_threads);
			result.bIsPositive = false;
		}
		else
		{
			BigNum::subtractNoCheck(bn1, bn2, result, num_threads);
			result.bIsPositive = true;
		}
	}
	else if (!bn1.IsPositive() && bn2.IsPositive())
	{
		if (bn1 < bn2)
		{
			BigNum::subtractNoCheck(bn2, bn1, result, num_threads);
			result.bIsPositive = true;
		}
		else
		{
			BigNum::subtractNoCheck(bn1, bn2, result, num_threads);
			result.bIsPositive = false;
		}
	}
	else if (!bn1.IsPositive() && !bn2.IsPositive())
	{
		BigNum::addNoCheck(bn1, bn2, result, num_threads);
		result.bIsPositive = false;
	}
}

void BigNum::addNoCheck(const BigNum &bn1, const BigNum &bn2, BigNum &result, int num_threads)
{
	pIntArrayType* resultsCarry = NULL;
	pIntArrayType* resultsNoCarry = NULL;

	try
	{
		unsigned int minSize = bn1.size < bn2.size ? bn1.size : bn2.size;
		unsigned int maxSize = bn1.size < bn2.size ? bn2.size : bn1.size;

		int minSize_plus_1 = minSize + 1;

		resultsCarry = new pIntArrayType[minSize_plus_1];
		resultsNoCarry = new pIntArrayType[minSize_plus_1];

		result.size = maxSize > minSize ? maxSize : minSize_plus_1;
		result.resizeArray(result.size, false);

		BigNum* largerSizedNum = const_cast<BigNum*>(bn1.size < bn2.size ? &bn2 : (bn1.size > bn2.size ? &bn1 : NULL));

		if (maxSize > minSize)
		{
			resultsNoCarry[minSize] = largerSizedNum->pIntArray[minSize];
			resultsCarry[minSize] = resultsNoCarry[minSize] + 1;
		}
		else
		{
			resultsNoCarry[minSize] = 0;
			resultsCarry[minSize] = 1;
		}

		int num_procs = omp_get_num_procs();

		if (num_procs < num_threads)
		{
			num_threads = num_procs;
		}

		omp_set_num_threads(num_threads);

		#pragma omp parallel
		{
			// MUST HAVE A BARRIER AFTER THIS FOR LOOP
			#pragma omp for
			for (int i = 0; i < minSize; i++)
			{
				resultsNoCarry[i] = bn1.pIntArray[i] + bn2.pIntArray[i];
				resultsCarry[i] = resultsNoCarry[i] + 1;
			}

			#pragma omp for nowait
			for(int i = 0; i < minSize_plus_1; i++)
			{
				unsigned char carryBit_NoCarry = 0, carryBit_Carry = 0, shouldCarry = 0;
				int shouldCarry_i = 0;

				while (shouldCarry_i < i)
				{
					carryBit_NoCarry = (unsigned char) (resultsNoCarry[shouldCarry_i] >> ((sizeof(pIntArrayType) * 8) - 1));
					carryBit_Carry = (unsigned char) (resultsCarry[shouldCarry_i] >> ((sizeof(pIntArrayType) * 8) - 1));
					shouldCarry = (shouldCarry & carryBit_Carry) | (!shouldCarry & carryBit_NoCarry);
					shouldCarry_i++;
				}

				if (shouldCarry)
				{
					result.pIntArray[i] = (resultsCarry[i] << 1) >> 1;
				}
				else
				{
					result.pIntArray[i] = (resultsNoCarry[i] << 1) >> 1;
				}
			}

			#pragma omp for nowait
			for (int i = minSize_plus_1; i < maxSize; i++)
			{
				result.pIntArray[i] = largerSizedNum->pIntArray[i];
			}
		}

		if (0 == result.pIntArray[result.size-1])
		{
			result.size--;
		}
	}
	catch (...)
	{
		delete[] resultsCarry;
		delete[] resultsNoCarry;
		throw;
	}

	delete[] resultsCarry;
	delete[] resultsNoCarry;
}

void BigNum::Subtract(const BigNum &bn1, const BigNum &bn2, BigNum &result, int num_threads)
{
	if (bn1.IsPositive() && bn2.IsPositive())
	{
		if (bn1 < bn2)
		{
			BigNum::subtractNoCheck(bn2, bn1, result, num_threads);
			result.bIsPositive = false;
		}
		else
		{
			BigNum::subtractNoCheck(bn1, bn2, result, num_threads);
			result.bIsPositive = true;
		}
	}
	else if (bn1.IsPositive() && !bn2.IsPositive())
	{
		BigNum::addNoCheck(bn1,bn2,result, num_threads);
		result.bIsPositive = true;
	}
	else if (!bn1.IsPositive() && bn2.IsPositive())
	{
		BigNum::addNoCheck(bn1, bn2, result, num_threads);
		result.bIsPositive = false;
	}
	else if (!bn1.IsPositive() && !bn2.IsPositive())
	{
		if (bn1 < bn2)
		{
			BigNum::subtractNoCheck(bn2, bn1, result, num_threads);
			result.bIsPositive = true;
		}
		else
		{
			BigNum::subtractNoCheck(bn1, bn2, result, num_threads);
			result.bIsPositive = false;
		}
	}
}

// required: bn1 > bn2
void BigNum::subtractNoCheck(const BigNum &bn1, const BigNum &bn2, BigNum &result, int num_threads)
{
	pIntArrayType* resultsBorrow = NULL;
	pIntArrayType* resultsNoBorrow = NULL;
	
	try
	{
		unsigned int minSize = bn1.size < bn2.size ? bn1.size : bn2.size;
		unsigned int maxSize = bn1.size < bn2.size ? bn2.size : bn1.size;

		resultsBorrow = new pIntArrayType[maxSize];
		resultsNoBorrow = new pIntArrayType[maxSize];

		result.size = maxSize;
		result.resizeArray(result.size, false);

		int num_procs = omp_get_num_procs();
		
		if (num_procs < num_threads)
		{
			num_threads = num_procs;
		}

		omp_set_num_threads(num_threads);

		#pragma omp parallel
		{
			#pragma omp for nowait
			for (int i = 0; i < minSize; i++)
			{
				resultsNoBorrow[i] = bn1.pIntArray[i] - bn2.pIntArray[i];
				resultsBorrow[i] = resultsNoBorrow[i] - 1;
			}

			// MUST HAVE A BARRIER AFTER THIS FOR LOOP
			#pragma omp for
			for (int i = minSize; i < maxSize; i++)
			{
				resultsNoBorrow[i] = bn1.pIntArray[i];
				resultsBorrow[i] = resultsNoBorrow[i] - 1;
			}

			#pragma omp for nowait
			for(int i = 0; i < maxSize; i++)
			{
				unsigned char borrowBit_NoBorrow = 0, borrowBit_Borrow = 0, shouldBorrow = 0;
				int shouldBorrow_i = 0;

				while (shouldBorrow_i < i)
				{
					borrowBit_NoBorrow = (unsigned char) (resultsNoBorrow[shouldBorrow_i] >> ((sizeof(pIntArrayType) * 8) - 1));
					borrowBit_Borrow = (unsigned char) (resultsBorrow[shouldBorrow_i] >> ((sizeof(pIntArrayType) * 8) - 1));
					shouldBorrow = (shouldBorrow & borrowBit_Borrow) | (!shouldBorrow & borrowBit_NoBorrow);
					shouldBorrow_i++;
				}

				if (shouldBorrow)
				{
					result.pIntArray[i] = (resultsBorrow[i] << 1) >> 1;
				}
				else
				{
					result.pIntArray[i] = (resultsNoBorrow[i] << 1) >> 1;
				}
			}
		}

		while (0 == result.pIntArray[result.size-1])
		{
			result.size--;
		}
	}
	catch (...)
	{
		delete[] resultsBorrow;
		delete[] resultsNoBorrow;
		throw;
	}

	delete[] resultsBorrow;
	delete[] resultsNoBorrow;
}

BigNum::BigNum()
	:pIntArray(NULL),
	 size(0)
{
	this->parse("0");
}

BigNum::BigNum(std::string number)
	:pIntArray(NULL),
	 size(0)
{
	this->parse(number);
}

BigNum::~BigNum()
{
	if (pIntArray)
	{
		delete[] pIntArray;
	}
}

std::string BigNum::GetNumber(const BigNum &bn)
{
	stringstream number;

	const int SIZE_NUMBER = sizeof(pIntArrayType) * 8;

	char strNumber[SIZE_NUMBER];
	
	for (int i = bn.size - 1; i >= 0; i--)
	{
		 BigNum_itoa(bn.pIntArray[i], strNumber, 2);
		 number << BigNum::getZeroString(strlen(strNumber) - 1);
		 number << strNumber;
	}

	if (!bn.bIsPositive)
	{
		stringstream ret;
		ret << '-' << bin2dec.Convert(number.str());
		return ret.str();
	}
	else
	{
		return bin2dec.Convert(number.str());
	}
}

void BigNum::parse(std::string number)
{
	if (number.at(0) == '-')
	{
		this->bIsPositive = false;

		number = number.substr(1,number.length() - 1);
	}
	else if (number.at(0) == '+')
	{
		this->bIsPositive = true;

		number = number.substr(1,number.length() - 1);
	}
	else
	{
		this->bIsPositive = true;
	}

	number = dec2bin.Convert(number);

	const int SIZE_NUMBER = sizeof(pIntArrayType) * 8 - 1;
	int i = number.length() - SIZE_NUMBER;

	while (i > 0)
	{
		number.insert(i," ");
		i -= SIZE_NUMBER;
		this->size++;
	}
	this->size++;

	char* numBeg = &number.at(0);
	char* numEnd = &numBeg[number.length()];

	this->capacity = this->size;
	pIntArray = new pIntArrayType[this->capacity];

	for (i = this->size - 1; i >= 0; i--)
	{
		pIntArray[i] =  BigNum_atoi(numBeg,&numBeg,2);
	}
}

const char* BigNum::getZeroString(int index)
{
	if (typeid(pIntArrayType) == typeid(unsigned long))
	{
		return ZERO_STRINGS_ul[index];
	}
	else if (typeid(pIntArrayType) == typeid(unsigned long long))
	{
		return ZERO_STRINGS_ull[index];
	}
}